package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 假设你总是可以到达数组的最后一个位置
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-06
 * Time:10:05
 */
public class DP45 {
    public int jump(int[] nums) {
        //状态定义F(i)表示当前到达最后位置的最小步数
        //状态转移方程:F(i) = Math.max(F(i -1) + nums[i],F(i))
        //赋初值F(0) = nums[0]
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {//表示能走到这一步
                end = maxPosition;//走到下一步
                steps++;
            }
        }
        return steps;
    }
}
